package main.java.indi.zyj.c150.array;

public class _03_reversePairs {

    static int count = 0;


    public static int reversePairs(int[] nums) {
        sort(nums, 0, nums.length - 1, new int[nums.length]);
        return count;
    }

    public static void sort(int[] nums, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            sort(nums, left, mid, temp);//归并排序左部分（left,mid)
            sort(nums, mid + 1, right, temp);//归并排序右部分(mid+1,right)
            merge(nums, left, mid, right, temp);//合并
        }
    }


    private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, index = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[index++] = nums[i++];
            } else {
                count += (mid - i + 1);//只需要这行代码
                temp[index++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = nums[i++];
        }
        while (j <= right) {
            temp[index++] = nums[j++];
        }
        index = 0;
        while (left <= right) {
            nums[left++] = temp[index++];
        }
    }
}
